#define DEBUG
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

typedef long long ll;

int min(int a, int b) {
	return a<b ? a : b;
}

class Hash {
	public:
		static const int size=1415113;
		int k[size], v[size];

		void add(int key, int val) {
			int p=key%size;
			for (; k[p]; p=(p+1)%size) {
				if (k[p]==key) {
					v[p] = min(v[p], val);
					return;
				}
			}
			k[p] = key;
			v[p] = val;
		}

		int get(int key, int def=-1) {
			int p=key%size;
			for (; k[p]; p=(p+1)%size) {
				if (k[p]==key) return v[p];
			}
			return def;
		}
};

ll qpower(ll a, int n, int p) {
	ll s=1;
	for (; n; n>>=1) {
		if (n&1) s=s*a%p;
		a = a*a%p;
	}
	return s;
}

int solve(ll a, ll b, int p) {
	static Hash h;
	memset(h.k, 0, sizeof h.k);
	int sp=sqrt(p-1);
	ll x=1;
	for (int i=0; i<sp; i++) {
		h.add(x, i);
		x = x*a%p;
	}
	ll now=1;
	for (int i=0; i<p; i+=sp) {
		int temp=h.get(b*qpower(now, p-2, p)%p);
		if (temp>=0) return i+temp+1;
		now = now*x%p;
	}
	return -1;
}

ll exgcd(int a, int b, ll &x, ll &y) {
	if (b==0) {
		x=1, y=0;
		return a;
	} else {
		ll tx, ty, ret;
		ret = exgcd(b, a%b, tx, ty);
		x = ty, y=tx-(a/b)*ty;
		return ret;
	}
}

int main() {
#ifdef DEBUG
	freopen("src.in", "r", stdin);
	freopen("src.out", "w", stdout);
#endif

	int t;
	scanf("%d", &t);
	for (int ti=1; ti<=t; ti++) {
		ll p, a, b, x, t;
		scanf("%lld %lld %lld %lld %lld", &p, &a, &b, &x, &t);
		if (x==t) printf("1\n");
		else if (a==0) {
			if (b==t) printf("2\n");
			else printf("-1\n");
		} else if (a==1) {
			if (b==0) printf("-1\n");
			else {
				ll u, v;
				exgcd(b, p, u, v);
				u = (u*(t-x+p)%p+p)%p;
				printf("%lld\n", u+1);
			}
		} else {
			ll u=(a*t-t+b+p)%p*qpower((x*a+b-x+p)%p, p-2, p)%p;
			printf("%d\n", solve(a, u, p));
		}
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}
